package _13_red_black_tree.case4;

import org.junit.Test;

import java.util.*;

/**
 * @author: mornd
 * @dateTime: 2023/6/17 - 23:00
 */
public class MyTest {
    @Test // 测试右旋
    public void testRightRotate() {
        RedBlackTree tree = new RedBlackTree();
        tree.root = new RedBlackTree.Node(8);
        RedBlackTree.Node yellow = new RedBlackTree.Node(5);
        yellow.parent = tree.root;
        tree.root.left = yellow;

        RedBlackTree.Node green = new RedBlackTree.Node(6);
        green.parent = yellow;
        yellow.right = green;
        tree.printTree();
        System.out.println();
        tree.rightRotate(tree.root);
        tree.root = yellow;
        tree.printTree();
    }

    @Test // 测试添加
    public void testPut() {
        RedBlackTree tree = new RedBlackTree();
        ArrayList<Integer> list = new ArrayList<>();
        for (int i = 1; i <= 20; i++) {
            list.add(i);
        }
        Collections.shuffle(list);
        for (Integer i : list) {
            tree.put(i, null);
        }
        tree.printTree();
    }

    @Test
    public void testRemove() {
        for (int i = 20; i > 0; i--) {
            RedBlackTree rbTree = genericTree();
            rbTree.remove(i);
            System.out.println("key=" + i);
            rbTree.printTree();
            System.out.println("\n\n------------------------------------\n\n");
        }
    }

    private RedBlackTree genericTree() {
        RedBlackTree rbTree = new RedBlackTree();
        for (int i = 1; i <= 20; i++) {
            rbTree.put(i, null);
        }
        return rbTree;
    }

    @Test
    public void testGet() {
        RedBlackTree rbTree = new RedBlackTree();
        for (int i = 1000000; i >=0; i--) {
            rbTree.put(i, null);
        }
        rbTree.printRBCount();
    }

    @Test // 100万数据，对应红色307367个，黑色692633个
    public void testRandomPut() {
        RedBlackTree rbTree = new RedBlackTree();

        int threshold = 1000000;
        Random rand = new Random();
        Set<Integer> set = new HashSet<>();
        while (set.size() < threshold) {
            int randNum = rand.nextInt(threshold) + 1;
            set.add(randNum);
        }
        for (int num : set) {
            rbTree.put(num, null);
        }
        rbTree.printRBCount();
    }
}
